package com.summli.basic.class04;

/**
 * 手写大根堆结构（基础类型的堆结构）
 * 提供插入
 * 提供弹出的方法
 * java中不能使用new T的形式，泛型擦除
 */
public class Code02_Heap01 {
    public static class MyMaxHeap {
        private int[] heap;
        private final int limit;
        private int heapSize;

        public MyMaxHeap(int limit) {
            heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }

        // 弹出数据之后，也需要维护整个数组的大根堆结构
        public int pop() {
            int maxInt = heap[0];
            swap(heap, 0, --heapSize);
            heapify(heap, 0, heapSize);
            return maxInt;
        }

        private void heapify(int[] heap, int index, int heapSize) {
            int left = 2 * index + 1;
            while (left < heapSize) {
                int large = left + 1 < heapSize && heap[left] < heap[left + 1] ? left + 1 : left;
                large = heap[index] < heap[large] ? large : index;
                if (large == index) break;
                swap(heap, index, large);
                index = large;
                left = 2 * index + 1;
            }
        }

        // 插入数据的时候，首先将数据插入数组中，并且通过heapInsert保障大根堆的数据结构
        public void push(int value) {
            if (isFull()) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            // 从下向上一次跟父进行比较，如果大于，交换，保证大根堆
            heapInsert(heap, heapSize++);
        }

        private void heapInsert(int[] arr, int index) {
            while (arr[index] > arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        public Boolean isEmpty() {
            return heapSize == 0;
        }

        public Boolean isFull() {
            return heapSize == limit;
        }
    }


    // For Test
    public static class RightMaxHeap {
        private int[] arr;
        private final int limit;
        private int size;

        public RightMaxHeap(int limit) {
            arr = new int[limit];
            this.limit = limit;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == limit;
        }

        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("heap is full");
            }
            arr[size++] = value;
        }

        public int pop() {
            int maxIndex = 0;
            for (int i = 1; i < size; i++) {
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            int ans = arr[maxIndex];
            arr[maxIndex] = arr[--size];
            return ans;
        }
    }

    // 对数器
    public static void main(String[] args) {
       /* MyMaxHeap heap = new MyMaxHeap(100);
        heap.push(2);
        heap.push(6);
        heap.push(3);
        heap.push(55);
        heap.push(153);
        heap.push(2423);
        heap.push(12);
        while(!heap.isEmpty()){
            System.out.println(heap.pop());
        }*/
        int value = 1000;
        int limit = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit) + 1;
            MyMaxHeap my = new MyMaxHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);
            for (int j = 0; j < curOpTimes; j++) {
                if (my.isEmpty() != test.isEmpty()) {
                    System.out.println("Empty Oops!");
                }
                if (my.isFull() != test.isFull()) {
                    System.out.println("Full Oops!");
                }
                if (my.isEmpty()) {
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                    test.push(curValue);
                } else if (my.isFull()) {
                    if (my.pop() != test.pop()) {
                        System.out.println("POP Oops!");
                    }
                } else {
                    if (Math.random() < 0.5) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else {
                        if (my.pop() != test.pop()) {
                            System.out.println("POP Oops!");
                        }
                    }
                }
            }
        }
        System.out.println("finish!");

    }
}
